//class Solution {
//public:
//    bool isUnivalTree(TreeNode* root) {
//        if (root == nullptr) return true;
//        if (root->left && root->val != root->left->val) return false;
//        if (root->right && root->val != root->right->val) return false;
//        return isUnivalTree(root->right) && isUnivalTree(root->left);
//    }
//};


//class Solution {
//public:
//    bool isSameTree(TreeNode* p, TreeNode* q) {
//        if (p == nullptr && q == nullptr) return true;
//        if (p == nullptr || q == nullptr) return false;
//        if (p->val != q->val) return false;
//        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//    }
//};




//class Solution {
//public:
//    bool isSameTree(TreeNode* p, TreeNode* q) {
//        if (p == nullptr && q == nullptr) return true;
//        if (p == nullptr || q == nullptr) return false;
//        queue<TreeNode*> q1, q2;
//        q1.push(p), q2.push(q);
//        while (!q1.empty() && !q2.empty())
//        {
//            TreeNode* val1 = q1.front();
//            q1.pop();
//            TreeNode* val2 = q2.front();
//            q2.pop();
//            if (val1 == nullptr && val2 == nullptr)continue;
//            if (val1 == nullptr || val2 == nullptr) return false;
//            if (val1->val != val2->val)  return false;
//            if (val1)
//            {
//                q1.push(val1->left);
//                q1.push(val1->right);
//            }
//            if (val2)
//            {
//                q2.push(val2->left);
//                q2.push(val2->right);
//            }
//        }
//        return q1.empty() && q2.empty();
//    }
//};




//class Solution {
//public:
//    bool isSymmetric(TreeNode* root) {
//        if (root == nullptr) return true;
//        return _isSymmetric(root->left, root->right);
//    }
//    bool _isSymmetric(TreeNode* root1, TreeNode* root2)
//    {
//        if (root1 == nullptr && root2 == nullptr) return true;
//        if (root1 == nullptr || root2 == nullptr) return false;
//        if (root1->val != root2->val) return false;
//        return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
//    }
//};





//class Solution {
//public:
//    bool isSymmetric(TreeNode* root) {
//        if (root == nullptr) return true;
//        queue<TreeNode*> q1, q2;
//        q1.push(root->left), q2.push(root->right);
//        while (!q1.empty() && !q2.empty())
//        {
//            TreeNode* val1 = q1.front(); q1.pop();
//            TreeNode* val2 = q2.front(); q2.pop();
//
//            if (val1 == nullptr && val2 == nullptr) continue;
//            if (val1 == nullptr || val2 == nullptr) return false;
//            if (val1->val != val2->val) return false;
//            q1.push(val1->left);
//            q2.push(val2->right);
//            q1.push(val1->right);
//            q2.push(val2->left);
//        }
//        return q1.empty() && q2.empty();
//    }
//};




//class Solution {
//public:
//    vector<int> ret;
//    vector<int> preorderTraversal(TreeNode* root) {
//        if (root == nullptr) return ret;
//        dfs(root);
//        return ret;
//    }
//    void dfs(TreeNode* root)
//    {
//        ret.push_back(root->val);
//        if (root->left)
//            dfs(root->left);
//        if (root->right)
//            dfs(root->right);
//    }
//};



//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//        stack<TreeNode*> st;
//        st.push(root);
//        while (!st.empty())
//        {
//            TreeNode* val = st.top(); st.pop();
//            ret.push_back(val->val);
//            if (val->right)
//                st.push(val->right);
//            if (val->left)
//                st.push(val->left);
//        }
//        return ret;
//    }
//};



//
//class Solution {
//public:
//    vector<int> ret;
//    vector<int> inorderTraversal(TreeNode* root) {
//        if (root == nullptr) return ret;
//        dfs(root);
//        return ret;
//    }
//    void dfs(TreeNode* root)
//    {
//        if (root->left == nullptr && root->right == nullptr)
//        {
//            ret.push_back(root->val);
//            return;
//        }
//        if (root->left)
//            dfs(root->left);
//        ret.push_back(root->val);
//        if (root->right)
//            dfs(root->right);
//        return;
//    }
//};



//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//        stack<TreeNode*> st;
//        TreeNode* cur = root;
//        while (cur || !st.empty())
//        {
//            while (cur)
//            {
//                st.push(cur);
//                cur = cur->left;
//            }
//            cur = st.top();
//            st.pop();
//            ret.push_back(cur->val);
//            cur = cur->right;
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    vector<int> ret;
//    vector<int> postorderTraversal(TreeNode* root) {
//        if (root == nullptr) return ret;
//        dfs(root);
//        return ret;
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root->left)
//            dfs(root->left);
//        if (root->right)
//            dfs(root->right);
//        ret.push_back(root->val);
//    }
//};





